package bfs;

import java.util.LinkedList;
import java.util.Queue;

//正难则反：
//    要的一个点能否到边界，就必须遍历到边界，如果不能到，就浪费了我时间
//    找到边界1，尽可能的往外扩，扩完后，剩余的1一定无法出去；

//本题可以采用： 单源/多源bfs 或者 dfs,但核心都是： 先处理边界1
public class 飞地数量 {
	public static int l,r;
    public static boolean[][] visit;
    public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public int numEnclaves(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        visit=new boolean[m][n];
        Queue<int[]> q=new LinkedList<>();
        //所有边界1入队列
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if((i==0||j==0||i==m-1||j==n-1)&&grid[i][j]==1){
                    visit[i][j]=true;
                    q.offer(new int[]{i,j});
                }
            }
        }
        //bfs-标记所有与边界1相连的连通块
        while(!q.isEmpty()){
            int sz=q.size();
            for(int i=0;i<sz;i++){
                int[] tmp=q.poll();
                int nx=tmp[0],ny=tmp[1];
                //枚举四个方向
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    //遍历下一层未经过的1
                    if(x>=0&&x<m&&y>=0&&y<n&&visit[x][y]==false&&grid[x][y]==1){
                        visit[x][y]=true;
                        q.offer(new int[]{x,y});
                    }
                }
            }
        }
        //收集中间1
        int ret=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(visit[i][j]==false&&grid[i][j]==1){
                    ret++;
                }
            }
        }
        return ret;
    }
}
